Міністерство освіти і науки України
Львівський національний університет ім. Івана Франка
Факультет прикладної математики та інформатики
Звіт
на тему:
“Метод Стеффенсена”
Розглядаючи метод Ньютона видно, що на кожній ітерації потрібно обраховувати матрицю других похідних. Звідси зрозуміло, що в тих випадках, коли обчислення матриці других похідних потребує значного об'єму обчислень, трудомісткість кожної ітерації методу Ньютона може бути обтяжуючою. Тому виникає питання, про можливість побудови методів мінімізації, які б по швидкості збігання не були гіршими від методу Ньютона, але для своєї реалізації не вимагали обчислення матриці других похідних. Одним з таких методів є метод Стеффенсена, який розроблявся для розв'язування нелінійних рівнянь. Використовуючи цей метод для розв'язування системи рівнянь , отримаємо наступний ітераційний метод розв'язування задачі мінімізації
(1)
Якщо наближення вже відомо, то наступне наближення визначається так:
(2)
де — числовий параметр, – матриця розділених різниць перших похідних, яка визначається за правилом
(3)
тут – елемент і - го рядка j - го стовпця матриці , a , позначають відповідно перші і другі похідні по змінних ui, uj функції J(u) i, j – (1,...,n); припускається, що при . Тоді з (3) випливає, що
, .
Це означає, що при , метод (2) перетворюється в метод Ньютона.
Як видно з (2), на кожному кроці методу Стеффенсена потрібно розв'язувати систему лінійних алгебраїчних рівнянь
(4)
Тут мається на увазі, що матриця не вироджена. Якщо при всіх J=1 … n, то згідно формули (3) для визначення елементів матриці достатньо знати перші похідні в точках u=uk і . Якщо ж при деякому j то в силу (3) для визначення j-ro стовпця матриці прийдеться обраховувати другі похідні в точці . Якщо при деякому k(0 виявилось J'( uk )=0, то процес (2) чи (4) припиняється: в цьому випадку uk– стаціонарна точка, і для вияснення, чи буде uk(U*, при необхідності потрібно провести додатковий експеримент. Тому будемо вважати, що . А тоді для визначення матриці потрібно буде обраховувати не всі другі похідні і в цьому випадку метод (2) має перевагу перед методом Ньютона. З іншої сторони, виявляється, метод (2) в класі сильно випуклих функції збігається з такою ж швидкістю, як і метод Ньютона.
Розглянемо реалізацію методу на основі функції
x*=(5,1,2)
x0=(0.5,0.5,0.5);
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, ExtCtrls, ComCtrls, StdCtrls, Buttons;
type
TForm1 = class(TForm)
StatusBar1: TStatusBar;
Panel1: TPanel;
StringGrid1: TStringGrid;
Panel2: TPanel;
SpeedButton1: TSpeedButton;
SpeedButton2: TSpeedButton;
procedure FormCreate(Sender: TObject);
Function f(x: Array of Double): Double;
Function fp1(x: Array of Double; c: Integer): Double;
procedure SpeedButton1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
Const
n=3;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.FormCreate(Sender: TObject);
begin
StringGrid1.Cells[0, 0] := 'K';
StringGrid1.Cells[1, 0] := 'X1';
StringGrid1.Cells[2, 0] := 'X2';
StringGrid1.Cells[3, 0] := 'X3';
StringGrid1.Cells[5, 0] := 'f(x)';
end;
Function TForm1.f(x: Array of Double): Double;
begin
Result :=sqr(x[0]-5)*(x[0]-5)+sqr(x[1]-1)*sqr(x[1]-1)+sqr(x[2]-2)*sqr(x[2]-2);
end;
Function TForm1.fp1(x: Array of Double; c: Integer): Double;
begin
Case c of
0: Result := 3*sqr(x[0]-5);
1: Result := 4*sqr(x[1]-1)*(x[1]-1);
2: Result := 4*sqr(x[2]-2)*(x[2]-2);
end;
end;
procedure TForm1.SpeedButton1Click(Sender: TObject);
var
x, x0, xh, Vektor1, Vektor2: array of Double;
M: array[0..n-1, 0..n-1] of Double;
i, j, k, iter: Integer;
eps,s1,s2,s3: Double;
begin
SetLength(x,n);
SetLength(x0,n);
SetLength(Vektor1, n);
SetLength(Vektor2, n);
SetLength(xh, n);
x[0] := 0;
x[1] := 0;
x[2] := 0;
...
